package acwing_03;

import java.util.Scanner;

public class _842_DFS_排列数字 {
	// 最大值为10，先进行初始化
	static int N = 10;
	static int path[] = new int[N+1];
	static boolean v[] = new boolean[N+1];
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		dfs(0,n);
		scan.close();
	}
	
	public static void dfs(int u,int n) {
		// 层数是从0开始的，当传入的层数跟n相同，说明已经搜索结束了
		if(u == n) {
			for(int i = 0; i < n; i++) {
				System.out.print(path[i] + " ");
			}
			System.out.println();
			return;
		}
		// v[i]用于判断该数值是否访问过
		// 遍历还没搜索过的值，通过该值继续下一层搜索，搜索完后要恢复访问过的数值为false
		// path中的值不需要恢复，因为后续的遍历会覆盖原值
		for(int i = 1; i <= n; i++) {
			if(!v[i]) {
				v[i] = true;
				path[u] = i;
				dfs(u+1,n);
				v[i] = false;
			}
		}
		
	}
}
